package main.leetcode.competition.weeklycomp.competition180;

import java.util.ArrayList;
import java.util.List;

/**
 * 5356.矩阵中的幸运树
 *
 * <p>给你一个 m * n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。
 *
 * <p>幸运数是指矩阵中满足同时下列两个条件的元素：
 *
 * <p>在同一行的所有元素中最小 在同一列的所有元素中最大
 *
 * <p>示例 1：
 *
 * <p>输入：matrix = [[3,7,8],[9,11,13],[15,16,17]] 输出：[15] 解释：15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。
 *
 * <p>示例2：
 *
 * <p>输入：matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]] 输出：[12] 解释：12
 * 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。
 *
 * <p>示例 3：
 *
 * <p>输入：matrix = [[7,8],[1,2]] 输出：[7]
 *
 * <p>提示：
 *
 * <p>m == mat.length n == mat[i].length 1 <= n, m <= 50 1 <= matrix[i][j] <= 10^5 矩阵中的所有元素都是不同的
 */
public class Solution1 {
    public static void main(String[] args) {
        System.out.println(
                new Solution1()
                        .luckyNumbers(new int[][] {{1, 10, 4, 2}, {9, 3, 8, 7}, {15, 16, 17, 12}}));
    }

    // 暴力法
    public List<Integer> luckyNumbers(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> list = new ArrayList<>();
        if (m == 1 && n == 1) {
            list.add(matrix[0][0]);
            return list;
        }
        int column;
        int i, j;
        int min;
        for (i = 0; i < m; i++) {
            column = 0;
            min = matrix[i][0];
            for (j = 1; j < n; j++) { // 找到每行的最小值和他对应的列值
                if (matrix[i][j] < min) {
                    min = matrix[i][j];
                    column = j;
                }
            }
            // 判断该最小值是否是当前列的最大值
            for (j = 0; j < m; j++) if (matrix[j][column] > min) break;

            // 上个循环未break
            if (j == m) list.add(min);
        }

        return list;
    }
}
